import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:编写一个算法来判断一个数 n 是不是快乐数。
 *
 * 「快乐数」定义为：
 *
 * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 * 如果这个过程 结果为 1，那么这个数就是快乐数。
 * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

 * User: 86189
 * Date: 2022-02-03
 * Time: 14:46
 */
public class Solution {
    //求数字n转换为各位数上平方和的函数
    public static int getNext(int n) {
        int ret=0;//最终的结果
        while(n>0) {
            int d=n%10;
            n=n/10;
            ret+=d*d;//各位数上的平方和
        }
        return  ret;

    }
    public static boolean isHappy(int n) {
        //对于这个判断快乐数的过程，有可能会陷入无限循环，那么这个数就不是快乐数，也就是只要判断的过程中出现了重复的数字那么就是快乐数
        //否则就可以最终到1，就是快乐数
        //对于这个判断的过程，我们可以利用哈希表去重来判断，还可以利用快慢指针就像判断链表是否有环类似的问题

        //哈希表法
        /*Set<Integer> set=new HashSet<>();
        while(n!=1 && !set.contains(n)) {
            set.add(n);
            n=getNext(n);
        }*/
        //return n==1;//当set.contains(n)时，那么当前n肯定不是1，所以n==1会返回false
        //当n是快乐数的时，n最后就会变成1，返回n==1那么就是true;

        //快慢指针法，去寻找是否有环，也就是在转换的过程中是否会出现重复的数字
        int slow=n;
        int fast=getNext(n);//先转换一次
        while(fast!=1 && slow!=fast){
            slow=getNext(slow);
            fast=getNext(getNext(fast));
        }
        return fast==1;//当fast==1时，是快乐数，返回true,当slow=fast时，说明出现了循环，那么fast就不会是1，返回false
    }

    public static void main(String[] args) {
        System.out.println(isHappy(116));
    }
}

